package backtrack;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Description 39. 组合总和 https://leetcode.cn/problems/combination-sum/
 * @Author Firenut
 * @Date 2023-02-06 19:55
 */
public class T39_combinationSum {
    @Test
    public void test() {
        combinationSum(new int[]{2, 3, 6, 7}, 7);
    }

    // 法3: 剪枝优化 将数组进行升序排序,如果target - candidates[index] < 0,也就没有必要递归下去了,
    // 因为candidates[index+1]>=candidates[index]
    public List<List<Integer>> combinationSum1(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        Arrays.sort(candidates); //升序排序
        dfs(0, list, ans, candidates, target);
        return ans;
    }
    void dfs2(int index,List<Integer>list,List<List<Integer>>ans,int[] candidates,int target){
        if (index >= candidates.length) {
            return;
        }
        if(target==0){
            ans.add(new ArrayList<>(list));
            return;
        }
        if (target - candidates[index] >= 0) { // 满足该条件才进行后续的递归
            list.add(candidates[index]); // 选
            dfs2(index, list, ans, candidates, target - candidates[index]);
            list.remove(list.size() - 1);  // 回溯
            dfs2(index + 1, list, ans, candidates, target);
        }
        // target - candidates[index] < 0 直接终止了
    }

    //针对法1,法2
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        dfs(0, list, ans, candidates, target);
        return ans;
    }

    // 法2: 基于法1的前提下,可以在进入递归前进行条件判断,只有符合条件才执行递归,从而减少递归的次数
    void dfs1(int index,List<Integer>list,List<List<Integer>>ans,int[] candidates,int target){
        if(index>=candidates.length){
            return;
        }
        if(target==0){
            ans.add(new ArrayList<>(list));
            return;
        }

        if (target - candidates[index] >= 0) { // 满足该条件才进行后续的递归
            list.add(candidates[index]); // 选
            dfs1(index, list, ans, candidates, target - candidates[index]);
            list.remove(list.size() - 1);  // 回溯
            dfs1(index + 1, list, ans, candidates, target);
        } else { //如果target-candidates[index]小于0,则不选该元素,index+1往下搜索
            dfs1(index + 1, list, ans, candidates, target);
        }
    }

    // 法1:
    void dfs(int index, List<Integer> list, List<List<Integer>> ans, int[] candidates, int target) {
        if (target < 0 || index >= candidates.length) {  // target < 0 必须要加
            return;
        }
        if (target == 0) {
            ans.add(new ArrayList<>(list));
            // System.out.println(list);
            return;
        }
        // 选中当前结点
        list.add(candidates[index]);
        dfs(index, list, ans, candidates, target - candidates[index]);
        // 回溯
        list.remove(list.size() - 1);
        // 不选当前结点
        dfs(index + 1, list, ans, candidates, target);
    }


}
